package lianxi;

import java.util.Scanner;

/**
 * 01 背包模版
 */
public class Main21 {
    public static void main(String[]args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int [][]f = new int[1010][1010];
        //存放每个物品的体积
        int []v = new int[1010];
        //存放价值
        int []w = new int[1010];
        for(int i=0;i<n;i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        //从第1 - i个物品
        for(int i=1;i<=n;i++) {
            for(int j=0;j<=m;j++) {
                f[i][j] = f[i-1][j];
                //j 的体积装不下第 i 个物品的时候时候为空集
                if( j >= v[i]) {
                    f[i][j] = Math.max(f[i][j] , f[i-1][ j-v[i] ]+w[i]);
                }
            }
        }
        System.out.print(f[n][m]);
    }
}
